﻿#define _CRT_SECURE_NO_WARNINGS 1

给定一个数组Ai
，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足1≤L
≤
R
≤
n
1≤L≤R≤n 的
L
L,
R
R，求出数组中第
L
L 至第
R
R 个元素的异或和。然后输出每组
L
L,
R
R 得到的结果加起来的值。

输入格式
输入的第一行包含一个整数
n
n。

第二行包含
n
n 个整数
A
i
A
i
​
，相邻整数之间使用一个空格分隔。

输出格式
输出一行包含一个整数表示答案。
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main() 
{
    int n; 
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 20; i >= 0; i--)
    {
        int s = 0;
        int n0 = 1, n1 = 0;
        for (int j = 0; j < n; j++)
        {
            int bit = (a[j] >> i) & 1;
            s += bit;
            //前缀和是奇数，合法区间个数=1+前面偶数的个数
            if (s % 2) 
            {
                ans += (1 << i) * n0;
                n1++;
            }
            else 
            {
                ans += (1 << i) * n1;
                n0++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
